package com.dexter.year2023.charpter1_linkedlist.level1;

/**
 * 链表的遍历、增删改查
 *
 * @author Dexter
 */
public class Demo2 {
    static class Node {
        public int val;
        public Node next;

        Node(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 遍历链表，获取长度
     *
     * @param head
     * @return
     */
    private static int getLength(Node head) {
        int length = 0;
        Node node = head;
        while (node != null) {
            length++;
            // 当前结点往后移动一位
            node = node.next;
        }
        return length;
    }

    /**
     * 添加结点
     *
     * @param head      头结点
     * @param insertOne 即将添加的结点
     * @param position  添加位置
     * @return
     */
    private static Node insertNode(Node head, Node insertOne, int position) {
        if (head == null) {
            return insertOne;
        }
        // 越界判断
        int size = getLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("添加位置越界");
            return head;
        }
        // 在头部添加
        if (position == 1) {
            insertOne.next = head;
            return insertOne;
        }
        // 在中间或尾部添加
        int count = 1;
        Node cur = head;
        // 让当前结点移动到 position - 1 结点位置
        while (count < position - 1) {
            cur = cur.next;
            count++;
        }
        // 移动到位，执行添加
        insertOne.next = cur.next;
        cur.next = insertOne;

        return head;
    }

    private static Node deleteNode(Node head, int position) {
        if (head == null) {
            return null;
        }
        // 越界判断
        int size = getLength(head);
        if (position > size || position < 1) {
            System.out.println("删除位置越界");
            return head;
        }
        // 在头部删除
        if (position == 1) {
            // 让头结点被垃圾回收
            return head.next;
        }
        // 在中间或尾部删除
        int count = 1;
        Node cur = head;
        while (count < position - 1) {
            cur = cur.next;
            count++;
        }
        // cur是前一个，cur.next是要删除的，cur.next.next是后一个
        cur.next = cur.next.next;
        return head;
    }

    /**
     * 打印成一个字符串
     *
     * @param head
     * @return
     */
    private static String toString(Node head) {
        Node cur = head;
        StringBuilder sb = new StringBuilder();
        while (cur != null) {
            sb.append(cur.val).append("\t");
            cur = cur.next;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        // 测试用例
        // 在头部添加 1
        Node head = new Node(1);
        System.out.println("在头部添加：" + head.val);
        System.out.println("当前链表：" + Demo2.toString(head) + "长度：" + getLength(head));

        // 在尾部添加 5
        Node node = new Node(5);
        head = insertNode(head, node, 2);
        System.out.println("在尾部添加：" + node.val);
        System.out.println("当前链表：" + Demo2.toString(head) + "长度：" + getLength(head));

        // 在中间添加 3
        node = new Node(3);
        head = insertNode(head, node, 2);
        System.out.println("在中间添加：" + node.val);
        System.out.println("当前链表：" + Demo2.toString(head) + "长度：" + getLength(head));

        // 在中间添加 2
        node = new Node(2);
        head = insertNode(head, node, 3);
        System.out.println("在中间添加：" + node.val);
        System.out.println("当前链表：" + Demo2.toString(head) + "长度：" + getLength(head));

        // 在头部删除
        head = deleteNode(head, 1);
        System.out.println("当前链表：" + Demo2.toString(head) + "长度：" + getLength(head));

        // 在中间删除
        head = deleteNode(head, 2);
        System.out.println("当前链表：" + Demo2.toString(head) + "长度：" + getLength(head));

        // 在尾部删除
        head = deleteNode(head, 2);
        System.out.println("当前链表：" + Demo2.toString(head) + "长度：" + getLength(head));
    }
}
